#!/usr/env/bin python
# -*- coding: utf-8 -*-

# @Time    : 2020-09-27 10:00 上午
# @Author  : yangdy
# @File    : 2020-09-27.235.二叉搜索树的最近公共祖先
# @Software: PyCharmCE
from tools.my_methods import *


# Definition for a binary tree node.
class TreeNode:
    def __init__(self, x):
        self.val = x
        self.left = None
        self.right = None


class Solution:
    def lowestCommonAncestor(self, root: 'TreeNode', p: 'TreeNode', q: 'TreeNode') -> 'TreeNode':
        # 1. 遍历数组，去最后一个相同的
        # def get_ancestors(rt, nd):
        #     ans = []
        #     if not rt or not nd:
        #         return ans
        #     nd_p = rt
        #     while nd_p:
        #         ans.append(nd_p)
        #         if nd_p == nd:
        #             break
        #         if nd_p.val > nd.val:
        #             nd_p = nd_p.left
        #         elif nd_p.val < nd.val:
        #             nd_p = nd_p.right
        #         else:
        #             break
        #     return ans
        # p_ancestors = get_ancestors(root, p)
        #
        # # for pi in p_ancestors:
        # #     print(pi.val, end=',')
        # # print(']')
        #
        # q_ancestors = get_ancestors(root, q)
        #
        # # for qi in q_ancestors:
        # #     print(qi.val, end=',')
        # # print(']')
        #
        # lp = len(p_ancestors)
        # lq = len(q_ancestors)
        # i = 0
        # while i < lp and i < lq:
        #     if p_ancestors[i].val != q_ancestors[i].val:
        #         break
        #     i += 1
        # ans = p_ancestors[i-1] if lp >= i > 0 and i <= lq else None
        # # print('ans:', ans.val)
        # return ans
        # 2.去最先出现的在p,q范围内的元素
        def dfs(rt, l, r):
            if not rt:
                return rt
            if rt.val < l:
                return dfs(rt.right, l, r)
            elif rt.val > r:
                return dfs(rt.left, l, r)
            return rt
        ans = dfs(root, min(p.val, q.val), max(p.val, q.val))
        # print(ans, ans.val)
        return ans


questions = [
    ([6, 2, 8, 0, 4, 7, 9, None, None, 3, 5], 2, 8,),
    ([6, 2, 8, 0, 4, 7, 9, None, None, 3, 5], 2, 4,),
]


def mk_data(data):
    rt = mk_tree(data[0], TreeNode)
    p_node = find_tree(rt, data[1])
    q_node = find_tree(rt, data[2])
    # display(rt)
    # print(p_node, q_node)
    # return rt, p_node, q_node
    return Solution().lowestCommonAncestor(rt, p_node, q_node)


work(questions, mk_data)
